// https://leetcode.cn/problems/median-of-two-sorted-arrays/submissions/
class Solution {
public:
    vector<int> mergeSort(vector<int>& nums1, vector<int>& nums2) {
        int l = 0, r = 0;
        vector<int> res;
        while (l < nums1.size() && r < nums2.size()) {
            if (nums1[l] < nums2[r]) {
                res.push_back(nums1[l++]);
            } else {
                res.push_back(nums2[r++]);
            }
        }
        while (l < nums1.size()) {
            res.push_back(nums1[l++]);
        }
        while (r < nums2.size()) {
            res.push_back(nums2[r++]);
        }
        return res;
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res = mergeSort(nums1, nums2);
        if (res.size() % 2 == 0) {
            return (double)(res[res.size() / 2 - 1] + res[res.size() / 2]) / 2;
        } else {
            return res[res.size() / 2];
        };
    }
};

// 二分查找 O(log (m+n))
class Solution {
public:
    int getKthElement(vector<int>& nums1, vector<int>& nums2, int k) {
        int m = nums1.size();
        int n = nums2.size();
        int idx1 = 0, idx2 = 0;
        while (idx1 < m && idx2 < n && k > 1) {
            int newidx1 = min(idx1 + k / 2 - 1, m - 1);
            int newidx2 = min(idx2 + k / 2 - 1, n - 1);
            if (nums1[newidx1] <= nums2[newidx2]) {
                k -= newidx1 - idx1 + 1;
                idx1 = newidx1 + 1;
            } else {
                k -= newidx2 - idx2 + 1;
                idx2 = newidx2 + 1;
            }
        }
        if (idx1 == m) return nums2[idx2 + k - 1]; // 注意
        if (idx2 == n) return nums1[idx1 + k - 1];
        return min(nums1[idx1], nums2[idx2]);
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        int total = m + n;
        if (total % 2 == 0) {
            return (getKthElement(nums1, nums2, total / 2 + 1) 
            + getKthElement(nums1, nums2, total / 2)) / 2.0;
        } else {
            return getKthElement(nums1, nums2, (total + 1) / 2);
        }
    }
};